package pearls;


public class BitmapSort {
	
	private static final int BYTE_SIZE = 8;

	/**
	 * Implementation of Jon Bentley's Bitmap Sort algorithm. The algorithm sorts
	 * an array of integers, with the given range for elements. 
	 * @param a input integer array
	 * @param min minimum value for elements in the array
	 * @param max maximum value for elements in the array
	 */
	public void sortDistinctIntegers(final int[] a, int min, int max){
		// Casts to long are used to avoid integer overflow in intermediate results
		int N = (int)(((long)max-min) / BYTE_SIZE + 1);
		byte[] bitmap = new byte[N]; //initialized to 0
		
		for(int arrayIndex = 0; arrayIndex < a.length; arrayIndex++){
			int byteAddress = (int)(((long)a[arrayIndex]-min)/BYTE_SIZE);
			int bitPosition = (int)(((long)a[arrayIndex]-min) % BYTE_SIZE);
			bitmap[byteAddress] |= 1 << bitPosition;
		}
		
		int arrayIndex = 0;
		for(int byteIndex = 0; byteIndex < N; byteIndex++){
			for(int bitIndex = 0; bitIndex < BYTE_SIZE; bitIndex++){
				// check if bit is set
				if((bitmap[byteIndex] & (1 << bitIndex)) > 0){
					a[arrayIndex] = byteIndex * BYTE_SIZE + bitIndex + min;
					arrayIndex++;
				}
			}
		}
	}
}
